# 15. 三数之和
# 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
#
# 注意：答案中不可以包含重复的三元组。
#
#
#
# 示例 1：
#
# 输入：nums = [-1,0,1,2,-1,-4]
# 输出：[[-1,-1,2],[-1,0,1]]
# 示例 2：
#
# 输入：nums = []
# 输出：[]
# 示例 3：
#
# 输入：nums = [0]
# 输出：[]
#
#
# 提示：
#
# 0 <= nums.length <= 3000
# -10^5 <= nums[i] <= 10^5
from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums_set = {}

        new_nums = []
        i = 0
        for each in nums:
            if each in nums_set:
                threshold = 2 if each else 3
                if len(nums_set[each]) < threshold:
                    nums_set[each].add(i)
                    new_nums.append(each)
                    i += 1
            else:
                nums_set[each] = {i}
                new_nums.append(each)
                i += 1
        collector = set()
        for i in range(len(new_nums) - 1):
            for j in range(i + 1, len(new_nums)):
                sum_ = new_nums[i] + new_nums[j]
                if -sum_ in nums_set:
                    for idx in nums_set[-sum_]:
                        if idx > j:
                            ss = [new_nums[i], new_nums[j], new_nums[idx]]
                            ss.sort()
                            collector.add(','.join(map(str, ss)))
        return [[int(each) for each in st.split(',')] for st in collector]


solution = Solution()
print(solution.threeSum([-1, 0, 1, 2, -1, -4]))
print(solution.threeSum([0] * 100))

ss = set()
ss.add(frozenset({1, 2, 3}))
ss.add(frozenset({2, 1, 3}))
ss.add(frozenset({3, 2, 1}))

print(ss)

